#include <iostream>
#include <vector>
#include <stack>
#include "IndexMinHeap.h"

using namespace std;

/**
 * 处理的是有权图,需要 Edge类
 * 图的描述 DenseGraph SparseGraph(应用更广)
 * 最小索引堆 数据结构辅助
 *
 * */
template<typename Graph, typename Weight>
class Dijkstra{

private:
    Graph &G;
    int s;				// 单源最短路径中的 源
    Weight *distTo;		// 原点s到每一个节点最短路径数据
    bool *marked;		// 已经找到最短路劲顶点进行标记
    vector<Edge<Weight>*> from;		// 记录到的顶点从哪来(参照广度优先遍历)

public:
    Dijkstra(Graph &graph, int s):G(graph){ // G 使用构造列表进行初始化

        this->s = s;
        distTo = new Weight[G.V()];
        marked = new bool[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
			// 不确定distTo 中元素类型
            distTo[i] = Weight();		// 使用模板类型Weight 默认构造函数
            marked[i] = false;
            from.push_back(NULL);
        }

		// 创建最小索引堆对象,开辟图中顶点个数空间
        IndexMinHeap<Weight> ipq(G.V());

        // 【start dijkstra】
        distTo[s] = Weight();		    // 对源点s初始化
        ipq.insert(s, distTo[s] );		// s压入最小索引堆,距离为 distTo[s]
        marked[s] = true;
        while( !ipq.isEmpty() ){		// 最小索引堆中元素存在
			// 找出当前最小索引堆中存在元素中,离源点最近的节点v
			// distTo[v] : 存储s到v 的最短距离
            int v = ipq.extractMinIndex();

            // distTo[v]就是s到v的最短距离
            marked[v] = true;				// 标记节点v
            //cout<<v<<endl;
			// 对节点v进行松弛操作,是否存在经过节点v到达另一个节点
			// 比不经过v到达另一个节点更短
            typename Graph::adjIterator adj(G, v);
			// 对 v的邻边进行遍历
            for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){
                int w = e->other(v);		// 找到 v的邻边断点w
                if( !marked[w] ){			// 还未找到s到w最短路径
					// 松弛判断,w是否被访问过form函数判断,
					// 或者这条边的权值 + 经过v的最短路径 < 到达w的最短路径
					// 进行松弛操作
                    if( from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){
                        distTo[w] = distTo[v] + e->wt();
                        from[w] = e;		// 更新从哪个节点过来的
						// 最小索引对中存在w,则进行更新,否则加入该节点
                        if( ipq.contain(w) )
                            ipq.change(w, distTo[w] );
                        else
                            ipq.insert(w, distTo[w] );
                    }
                }
            }
        }
    }

    ~Dijkstra(){
        delete[] distTo;
        delete[] marked;
    }

	// 源点s到w的最小权值
    Weight shortestPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        return distTo[w];
    }

	// 判断 s和 w 是否连通
    bool hasPathTo( int w ){
        assert( w >= 0 && w < G.V() );
        return marked[w];
    }

	// s 到 w存进 vector 中
    void shortestPath( int w, vector<Edge<Weight>> &vec ){

        assert( w >= 0 && w < G.V() );

		// 先将form数组将边倒序存入栈中,
		// 再将栈中元素放进 vector中 (参考无权图路径)
        stack<Edge<Weight>*> s;
        Edge<Weight> *e = from[w];
        while( e->v() != this->s ){
            s.push(e);
            e = from[e->v()];
        }
        s.push(e);

        while( !s.empty() ){
            e = s.top();
            vec.push_back( *e );
            s.pop();
        }
    }

	// 打印出最短路径的结果
    void showPath(int w){

        assert( w >= 0 && w < G.V() );

        vector<Edge<Weight>> vec;
        shortestPath(w, vec);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            cout<<vec[i].v()<<" -> ";
            if( i == vec.size()-1 )
                cout<<vec[i].w()<<endl;
        }
    }
};
